package com.sfx.算法专题.链表.删除链表;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-01
 * Time: 23:19
 */
public class Code_4_deleteDuplicates {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 递归
     */
    static class Solution1 {
        public ListNode deleteDuplicates(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            head.next = deleteDuplicates(head.next);
            if(head.val == head.next.val) head = head.next;
            return head;
        }
    }

    /**
     * 单指针
     */
    static class Solution2 {
        public ListNode deleteDuplicates(ListNode head) {
            if(head ==null ||head.next==null){
                return head;
            }
            ListNode cur = head;
            while(cur.next != null){
                if(cur.val == cur.next.val){
                    cur.next = cur.next.next;
                }else {
                    cur = cur.next;
                }
            }
            return head;
        }
    }

    /**
     * 双指针,一个指针tail表示有效链表结尾,一个cur遍历链表
     */
    static class Solution3 {
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null) return head;
            ListNode dummy = new ListNode(-109);
            ListNode tail = dummy;
            ListNode cur = head;
            while (cur != null) {
                // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
                if ( cur.next == null ||tail.val != cur.val) {
                    tail.next = cur;
                    tail = tail.next;
                }
                cur = cur.next;
            }
            tail.next = null;
            return dummy.next;
        }
    }
}